8761. Поиск в глубину – расстановка меток

 

Задан неориентированный граф. Запустите поиск в глубину из заданной вершины v. Выведите метки d[v] и f[v] для каждой вершины v в порядке возрастания вершин.

 

Вход. Первая строка содержит количество вершин n (n ≤ 100) и ребер m неориентированного графа. Вершины нумеруются начиная с 1. Каждая из следующих m строк содержит две вершины a и b – неориентированное ребро графа. Последняя строка содержит вершину v.

 

Выход. Запустите dfs(v). Выведите метки d[v] и f[v] для каждой вершины v (v = 1, 2, ..., n). Метки для каждой вершины следует выводить в отдельной строке.

 

Пример входа 1

Пример выхода 1

3 3

1 2

2 3

1 3

2

2 5

1 6

3 4

 

 

Пример входа 2

Пример выхода 2

5 5

1 2

2 3

2 5

2 4

1 4

3

3 6

2 9

1 10

4 5

7 8

 

 

РЕШЕНИЕ

графы – поиск в глубину

 

Анализ алгоритма

Построим матрицу смежности по списку ребер. Запустим поиск в глубину из заданной вершины v. Значения меток заносим в массивы d и f.

 

Реализация алгоритма

Объявим матрицу смежности g, массив лампочек used, а также массивы d и f. Объявим счетчик времени t.

 

#define MAX 101

int g[MAX][MAX], used[MAX];

int d[MAX], f[MAX];

int t;

 

Функция dfs совершает поиск в глубину из вершины v.

 

void dfs(int v)

{

 

Заносим метку входа.

 

  d[v] = t++;

 

Отмечаем вершину v как пройденную.

 

  used[v] = 1;

 

Перебираем вершины i, в которые можно пойти из v. В вершину i можно пойти из v, если между ними существует ребро (g[v][i] = 1) и вершина i еще не пройдена (used[i] = 0).

 

  for (int i = 1; i <= n; i++)

    if ((g[v][i] == 1) && (used[i] == 0)) dfs(i);

 

Заносим метку выхода.

 

  f[v] = t++;

}

 

Основная часть программы. Читаем количество вершин n и ребер m.

 

scanf("%d %d", &n, &m);

 

Обнуляем рабочие массивы.

 

memset(g, 0, sizeof(g));

memset(used, 0, sizeof(used));

 

Читаем список ребер. Строим матрицу смежности.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a][b] = g[b][a] = 1;

}

 

Читаем вершину v, устанавливаем время t = 1 и запускаем поиск в глубину из вершины v.

 

scanf("%d", &v);

t = 1;

dfs(v);

 

Выводим метки d[i] и f[i] для каждой вершины i.

 

for (i = 1; i <= n; i++)

  printf("%d %d\n", d[i], f[i]);

 

Python реализация – список смежности

Функция dfs совершает поиск в глубину из вершины v.

 

def dfs(v):

 

Функция использует глобальную переменную t.

 

  global t

 

Заносим метку входа. Увеличиваем время t на 1.

 

  d[v] = t

  t += 1

 

Отмечаем вершину v как пройденную.

 

  used[v] = True

 

Перебираем вершины to, в которые можно пойти из v. В вершину to можно пойти из v, если вершина to еще не пройдена (used[to] = 0).

 

  for to in g[v]:

    if not used[to]: dfs(to)

 

Заносим метку выхода. Увеличиваем время t на 1.

 

  f[v] = t

  t += 1

 

Основная часть программы. Читаем количество вершин n и ребер m.

 

n, m = map(int, input().split())

 

Создадим список смежности g и массив лампочек used.

 

g = [[] for _ in range(n+1)]

used = [False] * (n + 1)

 

Читаем список ребер. Строим список смежности.

 

for i in range(m):

  a, b = map(int, input().split())

  g[a].append(b)

  g[b].append(a)

 

Инициализируем списки d и f.

 

d = [0] * (n + 1)

f = [0] * (n + 1)

 

Читаем вершину v, устанавливаем время t = 1 и запускаем поиск в глубину из вершины v.

 

v = int(input())

t = 1

dfs(v)

 

Выводим метки d[i] и f[i] для каждой вершины i.

 

for i in range(1, n+1):

  print(d[i],f[i])